#ifndef DS_H_
#define DS_H_

#include "tools.hpp"
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iterator>
#include <list>
#include <queue>
#include <stdio.h>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


namespace lxj
{
// setAll功能的哈希表
class SetAllHashMap {

    std::unordered_map<int, std::pair<int, int>> _map;

    static inline int set_all_value = 1 << 31;
    static inline int set_all_time  = 1 << 31;
    static inline int cnt           = 0;

public:
    inline void put(int k, int v)
    {
        if (_map.find(k) == _map.end()) {
            _map.insert({k, {v, cnt++}});
        }
        else {
            _map.at(k).first  = v;
            _map.at(k).second = cnt++;
        }
    }

    inline void set_all(int value)
    {
        set_all_value = value;
        set_all_time  = cnt++;
    }

    inline int get(int index)
    {
        if (_map.find(index) == _map.end()) return 1 << 31;
        if (_map.at(index).second <= set_all_time) {
            return set_all_value;
        }
        else {
            return _map.at(index).first;
        }
    }
};

// 力扣146 实现LRU结构
template<class Key, class Value>
class LRUCache {

    std::list<Value> double_link;
    using Iter = typename std::list<Value>::iterator;

    std::unordered_map<Key, Iter> _map;
    size_t                        capacity;

    // 将iter换到链表尾部
    inline void swap(Iter iter)
    {
        Value temp = *iter;
        double_link.erase(iter);
        double_link.push_back(temp);
    }

public:
    LRUCache(int capacity) : capacity(capacity) {}

    inline Value get(Value key)
    {
        if (_map.find(key) == _map.end()) return ~Value{};
        swap(_map.at(key));
        Iter back_iter = double_link.end();
        std::advance(back_iter, -1);
        _map.at(key) = back_iter;
        return *_map[key];
    }

    inline void put(Key key, Value value)
    {
        if (_map.find(key) != _map.end()) {
            swap(_map.at(key));
            Iter back_iter = double_link.end();
            std::advance(back_iter, -1);
            _map.at(key) = back_iter;
            *back_iter   = value;
            return;
        }

        if (double_link.size() < capacity) {
            double_link.push_back(value);
            Iter back_iter = double_link.end();
            std::advance(back_iter, -1);
            _map.insert({key, back_iter});
        }
        else {
            Iter begin = double_link.begin();
            Key  del_key;
            for (auto& pair : _map) {
                if (pair.second == begin) {
                    del_key = pair.first;
                    break;
                }
            }
            _map.erase(del_key);
            double_link.pop_front();

            double_link.push_back(value);
            Iter back_iter = double_link.end();
            std::advance(back_iter, -1);
            _map.insert({key, back_iter});
        }
    }
};

// 力扣380 插入，删除和获取随机元素O(1)时间的结构
template<class T>
class RandomizedSet {
    inline static T               _arr[200000] = {};
    std::unordered_map<T, size_t> _map;
    size_t                        _size;
    inline static auto&           random = lxj::Random<int>::instance();

public:
    RandomizedSet() : _size(0) {}
    ~RandomizedSet() {}

    inline bool insert(T val)
    {
        if (_map.count(val)) return false;
        _arr[_size] = val;
        _map.insert({val, _size});
        _size++;
        return true;
    }

    inline bool remove(T val)
    {
        if (_map.count(val) == 0) return false;
        size_t index      = _map[val];
        _arr[index]       = _arr[_size - 1];
        _map[_arr[index]] = index;
        _map.erase(val);
        _size--;
        return true;
    }

    inline T getRandom()
    {
        if (_size == 0) return T{};
        return _arr[random(0, _size - 1)];
    }
};

// 力扣381 O(1) 时间插入、删除和获取随机元素 - 允许重复
template<class T>
class RandomizedCollection {
    std::vector<T>                                    _arr;
    std::unordered_map<T, std::unordered_set<size_t>> _map;
    inline static auto&                               random = lxj::Random<int>::instance();

public:
    RandomizedCollection() {}

    inline bool insert(T val)
    {
        _arr.push_back(val);
        const bool b = _map.count(val) == 0 ? true : false;
        _map[val].insert(_arr.size() - 1);
        return b;
    }

    inline bool remove(T val)
    {
        if (_map.count(val) == 0) return false;

        /* size_t index     = *_map[val].begin();
        size_t _size     = _arr.size();
        _arr[index]=_arr[_size-1];
        _map[val].erase(index);
        _map[_arr[index]].insert(index);
        _map[_arr[index]].erase(_size - 1);
        _arr.pop_back();
        if (_map[val].empty()) {
            _map.erase(val);
        } */

        size_t index     = *_map[val].begin();
        size_t _size     = _arr.size();
        T      end_value = _arr[_size - 1];
        if (val == end_value) {
            _map[val].erase(_size - 1);
        }
        else {
            _map[end_value].insert(index);
            _arr[index] = end_value;
            _map[end_value].erase(_size - 1);
            _map[val].erase(index);
        }
        _arr.pop_back();
        if (_map[val].empty()) _map.erase(val);
        return true;
    }

    inline T getRandom()
    {
        if (_arr.size() == 0) return ~T{};
        return _arr[random(0, _arr.size() - 1)];
    }
};

// 力扣295 快速获取数据流中位数的结构
template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
class MedianFinder {
    std::priority_queue<T, std::vector<T>, std::less<T>>    max_que;
    std::priority_queue<T, std::vector<T>, std::greater<T>> min_que;

    inline void balance()
    {
        size_t max  = max_que.size();
        size_t min  = min_que.size();
        size_t diff = max > min ? max - min : min - max;
        if (diff == 2) {
            if (max_que.size() > min_que.size()) {
                min_que.push(max_que.top());
                max_que.pop();
            }
            else {
                max_que.push(min_que.top());
                min_que.pop();
            }
        }
    }

public:
    MedianFinder() {}

    inline void addNum(T num)
    {
        if (max_que.empty() || max_que.top() >= num) {
            max_que.push(num);
        }
        else {
            min_que.push(num);
        }
        balance();
    }

    inline double findMedian()
    {
        if (max_que.size() == min_que.size()) {
            return (double)(max_que.top() + min_que.top()) / 2;
        }
        else {
            return max_que.size() > min_que.size() ? max_que.top() : min_que.top();
        }
    }
};

// 力扣895 最大频率栈
template<class T = int, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
class FreqStack {
    // 出现的最大次数
    size_t top_times;
    // 每一个数出现了几次
    std::unordered_map<T, size_t> value_times;
    // 每层节点
    std::unordered_map<size_t, std::list<T>> cnt_values;

public:
    FreqStack() : top_times(0) {}

    inline void push(T val)
    {
        value_times[val]++;
        top_times = top_times < value_times[val] ? value_times[val] : top_times;
        cnt_values[value_times[val]].push_back(val);
    }

    inline T pop()
    {
        if (cnt_values.empty()) return ~T{};
        T ans = cnt_values[top_times].back();
        value_times[ans]--;
        cnt_values[top_times].pop_back();
        if (value_times[ans] == 0) {
            value_times.erase(ans);
        }
        if (cnt_values[top_times].empty()) {
            cnt_values.erase(top_times);
            top_times--;
        }
        return ans;
    }

    inline bool empty() { return cnt_values.empty(); }
};

// 力扣432. 全 O(1) 的数据结构
class AllOne {
    struct Bucket {
        std::unordered_set<std::string> set;
        size_t                          cnt;
        Bucket*                         last;
        Bucket*                         next;

        Bucket(const std::string& s, size_t n) : cnt(n), last(nullptr), next(nullptr)
        {
            set.insert(s);
        }
    };

    Bucket*                                  head;
    Bucket*                                  tail;
    std::unordered_map<std::string, Bucket*> map;

private:
    inline static void insert(Bucket* cur, Bucket* pos)
    {
        pos->next       = cur->next;
        cur->next       = pos;
        pos->next->last = pos;
        pos->last       = cur;
    }

    inline static void remove(Bucket* cur)
    {
        cur->last->next = cur->next;
        cur->next->last = cur->last;
        cur->next       = nullptr;
        cur->last       = nullptr;

        delete cur;
        cur = nullptr;
    }

public:
    AllOne() : head(new Bucket("", 0)), tail(new Bucket("", INT64_MAX))
    {
        head->next = tail;
        tail->last = head;
    }

    ~AllOne()
    {
        while (head != nullptr) {
            auto cur = head;
            head     = head->last;
            delete cur;
            cur = nullptr;
        }
        map.clear();
    }

    inline void inc(std::string key)
    {
        if (map.find(key) == map.end()) {
            if (head->next->cnt == 1) {
                map[key] = head->next;
                head->next->set.insert(key);
            }
            else {
                Bucket* new_bucket = new Bucket(key, 1);
                map.insert({key, new_bucket});
                insert(head, new_bucket);
            }
        }
        else {
            Bucket* bucket = map[key];
            if (bucket->next->cnt == bucket->cnt + 1) {
                map[key] = bucket->next;
                bucket->next->set.insert(key);
            }
            else {
                Bucket* new_bucket = new Bucket(key, bucket->cnt + 1);
                map[key]           = new_bucket;
                insert(bucket, new_bucket);
            }
            bucket->set.erase(key);
            if (bucket->set.empty()) remove(bucket);
        }
    }

    inline void dec(std::string key)
    {
        if (map.find(key) == map.end()) return;

        Bucket* bucket = map[key];
        if (bucket->cnt == 1) {
            map.erase(key);
        }
        else {
            if (bucket->last->cnt == bucket->cnt - 1) {
                map[key] = bucket->last;
                bucket->last->set.insert(key);
            }
            else {
                Bucket* new_bucket = new Bucket(key, bucket->cnt - 1);
                map[key]           = new_bucket;
                insert(bucket->last, new_bucket);
            }
        }
        bucket->set.erase(key);
        if (bucket->set.empty()) remove(bucket);
    }

    inline std::string getMaxKey() { return *tail->last->set.cbegin(); }

    inline std::string getMinKey() { return *head->next->set.cbegin(); }
};

}   // namespace lxj

#endif